/*
 * BST.cpp
 *
 *  Created on: 23-03-2012
 *      Author: Hanna Sienkiewicz
 */


#include <cstddef>
#include <iostream>
#include <sys/time.h>
#include <cstdlib>
#include "BST.h"

using namespace std;


bst::bst() {
	korzen=NULL;
	licznik=0;
}

typedef unsigned long long timestamp; // zmiena przechowujaca czas;

	// funkcja do mierzenia czasu
	static timestamp gettimestamp(){
		struct timeval now;
		gettimeofday(&now,NULL);
		return now.tv_usec+(timestamp)now.tv_sec*1000000;
	}

void bst:: performance(int tab[], int size, int tabadd[], int sizeadd)
{
	double time=0.0;
	for(int i=0;i<10;i++){
		time+=addperformance(tab,size,tabadd,sizeadd);
	}
	time/=10;
	cout << "\n\nSredni czas dodawania dla DRZREWA PRZESZUKIWAN BINARNYCH [przed: " << size << " po: " << sizeadd+size << "] = "  << time << " sekund\n";

	time=0.0;
		for(int i=0;i<10;i++){
			time+=deleteperformance(tab,size);
		}
		time/=10;
		cout << "Sredni czas usunięcia wszystkiego dla DRZEWA PRZESZUKIWAN BINARNYCH [dla: " << size << " elementow "  << "] = "  << time << " sekund\n\n\n";
}



double bst:: deleteperformance(int tab[], int size){
	wyczysc();
	for(int i=0;i<size;i++){
		dodaj(tab[i]);
	}
	timestamp t0=gettimestamp();

	for(int i=0;i<size;i++){
		usun(korzen->wartosc);
	}
	timestamp t1=gettimestamp();
	return (t1-t0)/1000000.0L;
}

double bst:: addperformance(int tab[], int size, int tabadd[], int sizeadd){
	wyczysc();
	for(int i=0;i<size;i++){
		dodaj(tab[i]);
	}
	timestamp t0=gettimestamp();
	for(int i=0;i<sizeadd;i++){
		dodaj(tabadd[i]);
	}
	timestamp t1=gettimestamp();
	return (t1-t0)/1000000.0L;
}

void bst::dodajwezel(wezel *wel, int a)
{
	if(wel->wartosc>=a)
	{
		if (wel->lewy!=NULL)
		{
			dodajwezel(wel->lewy,a);
		} else
		{
			wezel *temp=new wezel(wel,a);
			wel->lewy=temp;
		}
	} else
	{
		if (wel->prawy!=NULL)
		{
			dodajwezel(wel->prawy,a);
		} else
		{
			wezel *temp=new wezel(wel,a);
			wel->prawy=temp;
		}
	}
}
void bst::dodaj(int a)
{
	if(licznik==0)
	{
		if(korzen!=NULL){
			delete korzen;
		}
		korzen=new wezel(NULL,0);
		korzen->lewy=NULL;
		korzen->prawy=NULL;
		korzen->wartosc=a;
	}
	else
	{
		dodajwezel(korzen,a);
	}
	licznik++;
}

void bst:: wyswietl()
{
	wyswietlwezel(korzen);
	cout << "\n";
}

void bst:: wyswietlwezel(wezel *wel)
{
	if(wel!=NULL){
		if(wel->lewy!=NULL)
		{
			wyswietlwezel(wel->lewy);
		}
		cout<<wel->wartosc<<", ";
		if(wel->prawy!=NULL)
		{
			wyswietlwezel(wel->prawy);
		}
	} else {
		cout << "[DRZEWO JEST PUSTE]\n";
	}
}

void bst:: wyczysc()
{
	wyczyscwezel(korzen);
	//cout << "\n [ DZEWO JEST PUSTE !!! ]\n";
	korzen=NULL;
	licznik=0;
}

void bst:: wyczyscwezel(wezel *wel)
{
	if(wel!=NULL){
		if(wel->lewy!=NULL)
		{
			wyczyscwezel(wel->lewy);
		}
		if(wel->prawy!=NULL)
		{
			wyczyscwezel(wel->prawy);
		}
		wel->rodzic=NULL;
		wel->lewy=NULL;
		wel->prawy=NULL;
		delete wel;
	}
}

wezel* bst:: poprzednik(wezel *wel)
{
	if(wel->prawy==NULL){
		return wel;
	} else {
		return poprzednik(wel->prawy);
	}
}

wezel* bst:: nastepnik(wezel *wel)
{
	if(wel->lewy==NULL){
//		wezel *tmp=wel->rodzic;
//		if(tmp->prawy==wel){
//			tmp->prawy=wel->prawy;
//		} else {
//			tmp->lewy=wel->prawy;
//		}
//		wel->prawy=tmp;
		return wel;
	} else {
		return nastepnik(wel->lewy);
	}
}

void bst:: usunElement(wezel *wel)
{
	wezel *podrzewo;
	wezel *ojciec=wel->rodzic;
	if (wel->lewy!=NULL){
		podrzewo=wel->lewy;
	} else {
		podrzewo=wel->prawy;
	}

	if(ojciec==NULL){
		korzen=podrzewo;
	} else if (ojciec->lewy==wel){
		ojciec->lewy=podrzewo;
	} else {
		ojciec->prawy=podrzewo;
	}
	if(podrzewo!=NULL&&ojciec!=NULL){
		podrzewo->rodzic=ojciec;
	}
	delete wel;
}

int bst:: root(){
	return korzen->wartosc;
}

void bst:: usun(int b)
{
	wezel *tmp=znajdz(korzen,b);
	if(tmp!=NULL){
		if(tmp->lewy==NULL&&tmp->prawy==NULL){
			usunElement(tmp);
		} else {
			if(tmp->lewy!=NULL){
				 wezel *przenies=poprzednik(tmp->lewy);
				 tmp->wartosc=przenies->wartosc;
				 usunElement(przenies);
			 } else {
				 wezel *przenies=nastepnik(tmp->prawy);
				 tmp->wartosc=przenies->wartosc;
				 usunElement(przenies);
			 }
		}
		licznik--;
	}
}


wezel* bst:: znajdz(wezel *wel, int a){
	if(wel->wartosc==a)
	{
		return wel;
	} else {
		if(wel->wartosc>a)
		{
			if(wel->lewy!=NULL)
			{
				return znajdz(wel->lewy,a);
			} else
			{
				cout << "\n [ NIE ZNALEZIONO WARTOSCI !!! ]\n";
				return NULL;
			}
		} else {
			if(wel->prawy!=NULL)
			{
				return znajdz(wel->prawy,a);
			} else
			{
				cout << "\n [ NIE ZNALEZIONO WARTOSCI !!! ]\n";
			return NULL;
			}
		}
	}
}
bst::~bst() {
	delete korzen;
}




